package src.leetcode.hot.mid_0120;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author liyizzz
 * @description 三角形最小路径和
 * @date 2024/12/19 16:08
 */
public class minimumTotal {
    public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> list1 = new ArrayList<>(List.of(2)); list.add(list1);
        List<Integer> list2 = new ArrayList<>(List.of(3, 4)); list.add(list2);
        List<Integer> list3 = new ArrayList<>(List.of(6,5,7)); list.add(list3);
        List<Integer> list4 = new ArrayList<>(List.of(4,1,8,3)); list.add(list4);
        System.out.println(solution.minimumTotal(list));
    }
}

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        if (n <= 0) return -1;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            List<Integer> t = triangle.get(i);
            for (int j = i; j > 0; j--) {
                dp[j] = Math.min(dp[j], dp[j - 1]) + t.get(j);
            }
            dp[0] = t.get(0) + dp[0];
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            ans = Math.min(ans, dp[i]);
        }
        return ans;
    }
}